{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 延迟指标"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| 标                                              | 说明                                                         | 典型用途                                                     | 计算方法（示例符号：一次测试共有 $n$ 次请求，每次延迟为 $L_i$） |\n",
    "| ----------------------------------------------- | ------------------------------------------------------------ | ------------------------------------------------------------ | ------------------------------------------------------------ |\n",
    "| 吞吐量（Throughput）                            | 指系统在单位时间内完成的工作量，例如每秒处理的请求数、成交数等。 | 衡量系统整体处理能力，评估扩展性、硬件资源利用率。           | $\\text{Throughput} = \\frac{\\text{总完成任务数}}{\\text{观测时长}}$ 例如：1 分钟内完成 12 000 次请求，则吞吐量 = $12 000 / 60 = 200$ RPS。 |\n",
    "| 平均延迟（Mean Latency）                        | 所有延迟样本的算术平均值，对偶发的高延迟非常敏感。           | 初步评估系统响应时间，适用于延迟分布较稳定的系统。           | $\\bar{L} = \\frac{1}{n}\\sum_{i=1}^{n} L_i$                    |\n",
    "| 中位数延迟（Median Latency, P50）               | 将延迟样本从小到大排序后位于中间位置的值，受极端值影响较小。 | 衡量“典型”请求的响应时间；对非对称或长尾延迟分布更稳健。     | 若 $n$ 为奇数：中位数 = 第 $(n+1)/2$ 个值；若 $n$ 为偶数：中位数 = 两个中间值的平均。 |\n",
    "| 峰值延迟（Tail / Max Latency，例如 P99、P99.9） | 关注最慢的请求，常用分位数（如 99%、99.9%）或直接取最大值。  | 评估最坏情况下的用户体验，发现尾部延迟问题。                 | **最大值**：$\\max(L_1, L_2, \\ldots, L_n)$;  **分位数**：排序后取位置 $\\lceil p \\times n \\rceil$ 的样本（如 $p = 0.99$ 表示 P99）。 |\n",
    "| 延迟方差（Variance of Latency）                 | 衡量延迟波动程度；方差越小，延迟越稳定。                     | 对需保证延迟可预测性的系统（如电子交易、实时控制）尤为重要。 | $\\sigma^2 = \\frac{1}{n}\\sum_{i=1}^{n} (L_i - \\bar{L})^2$ 常配合标准差 $\\sigma = \\sqrt{\\sigma^2}$ 使用。 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 对延迟敏感型应用程序的要求的性能特征"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| 要求                   | 含义 / 关注点                                                | 常用指标                                                     | 计算 / 衡量方法                                              |\n",
    "| ---------------------- | ------------------------------------------------------------ | ------------------------------------------------------------ | ------------------------------------------------------------ |\n",
    "| 正确性与稳健性         | 系统必须维持近乎 100% 的正确输出，对异常与故障具备高容错能力；能在负载增长或场景变化时保持稳定。 | 错误率、成功率、可用性 (Availability)、平均故障间隔时间 (MTBF)、平均修复时间 (MTTR)。 | **错误率**：$\\text{Error Rate} = \\frac{\\text{错误请求数}}{\\text{总请求数}}$。<br>**可用性**：$\\text{Availability} = \\frac{\\text{正常运行时间}}{\\text{总时间}}$。<br>**MTBF**：记录两次故障之间间隔的平均值；**MTTR**：修复时长的平均值。 |\n",
    "| 平均低延迟             | 绝大多数请求需在较短时间内完成，避免平均响应时间过长。       | 平均延迟 (Mean Latency)、中位数延迟 (P50)。                  | $\\bar{L} = \\frac{1}{n}\\sum_{i=1}^{n} L_i$。<br>中位数：对 $L_i$ 排序后取中间值；若样本偶数，取两中间值平均。 |\n",
    "| 峰值延迟上限           | 延迟的最长时间必须可控，不能出现极端长尾。                   | 99 分位延迟（P99）、99.9 分位延迟（P99.9）、最大延迟 (Max Latency)。 | **分位数**：对延迟样本排序，取位置 $\\lceil p \\times n \\rceil$ 的值（如 $p=0.99$）。<br>**最大值**：$\\max(L_1,\\ldots,L_n)$。设置阈值确保尾部延迟受控。 |\n",
    "| 可预测的延迟 —— 低抖动 | 延迟波动（抖动）要尽量小，保持可预测性。                     | 延迟方差 / 标准差、瞬时抖动 (Jitter)。                       | $\\sigma^2 = \\frac{1}{n}\\sum_{i=1}^{n}(L_i - \\bar{L})^2$，标准差 $\\sigma = \\sqrt{\\sigma^2}$。<br>网络抖动可用相邻样本差的平均值：(\\text{Jitter} = \\frac{1}{n-1}\\sum_{i=2}^{n} |\n",
    "| 高吞吐量               | 在保证低延迟的同时最大化单位时间内完成的任务数量。           | 吞吐量 (Throughput)、每核吞吐 (Throughput per core)。        | $\\text{Throughput} = \\frac{\\text{总完成任务数}}{\\text{观测时长}}$。<br>每核吞吐：$\\text{Throughput per core} = \\frac{\\text{总吞吐量}}{\\text{活跃 CPU 核数}}$。通过压测不同并发度评估延迟与吞吐折中。 |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Pointer Aliasing"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// 别名分析限制优化：编译器必须假设 a 和 b 可能指向同一块内存，因此不能把 *b 的读取移出循环，也不能提前矢量化。\n",
    "\n",
    "void func(int* a, int* b, int n) {\n",
    "    for(int i = 0; i < n; ++i) {\n",
    "        a[i] = *b;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// restrict 提示优化：告诉编译器 a 与 b 没有重叠，因而 *b 可被 hoist 到循环外，生成的汇编通常会包含加载一次然后矢量化更新的指令序列，减少访存次数。\n",
    "\n",
    "void func(int * restrict a, int * restrict b, int n) {\n",
    "    for (int i = 0; i < n; ++i) {\n",
    "        a[i] = *b;\n",
    "    }\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [],
   "source": [
    "! cd pointer_aliasing && g++ -O3 benchmark_alias.cpp -lbenchmark -lpthread -o bench_alias"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2025-10-09T10:09:06+08:00\n",
      "Running ./bench_alias\n",
      "Run on (16 X 3792.93 MHz CPU s)\n",
      "CPU Caches:\n",
      "  L1 Data 32 KiB (x8)\n",
      "  L1 Instruction 32 KiB (x8)\n",
      "  L2 Unified 1024 KiB (x8)\n",
      "  L3 Unified 16384 KiB (x1)\n",
      "Load Average: 0.52, 0.31, 0.18\n",
      "----------------------------------------------------------\n",
      "Benchmark                Time             CPU   Iterations\n",
      "----------------------------------------------------------\n",
      "BM_FuncAlias         67227 ns        67227 ns         9939\n",
      "BM_FuncRestrict      64708 ns        64709 ns        11278\n"
     ]
    }
   ],
   "source": [
    "! cd pointer_aliasing && ./bench_alias"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [],
   "source": [
    "! cd pointer_aliasing && g++ -O3 -fstrict-aliasing benchmark_alias.cpp -lbenchmark -lpthread -o bench_alias"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2025-10-09T10:09:40+08:00\n",
      "Running ./bench_alias\n",
      "Run on (16 X 3792.93 MHz CPU s)\n",
      "CPU Caches:\n",
      "  L1 Data 32 KiB (x8)\n",
      "  L1 Instruction 32 KiB (x8)\n",
      "  L2 Unified 1024 KiB (x8)\n",
      "  L3 Unified 16384 KiB (x1)\n",
      "Load Average: 0.53, 0.33, 0.19\n",
      "----------------------------------------------------------\n",
      "Benchmark                Time             CPU   Iterations\n",
      "----------------------------------------------------------\n",
      "BM_FuncAlias         63998 ns        63996 ns        10888\n",
      "BM_FuncRestrict      63060 ns        63060 ns        11606\n"
     ]
    }
   ],
   "source": [
    "! cd pointer_aliasing && ./bench_alias"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2025-10-09T10:11:10+08:00\n",
      "Running ./bench_alias\n",
      "Run on (16 X 3792.93 MHz CPU s)\n",
      "CPU Caches:\n",
      "  L1 Data 32 KiB (x8)\n",
      "  L1 Instruction 32 KiB (x8)\n",
      "  L2 Unified 1024 KiB (x8)\n",
      "  L3 Unified 16384 KiB (x1)\n",
      "Load Average: 0.86, 0.58, 0.29\n",
      "-----------------------------------------------------------------\n",
      "Benchmark                       Time             CPU   Iterations\n",
      "-----------------------------------------------------------------\n",
      "BM_FuncAlias_mean           70041 ns        70025 ns            5\n",
      "BM_FuncAlias_median         64420 ns        64418 ns            5\n",
      "BM_FuncAlias_stddev         12978 ns        12942 ns            5\n",
      "BM_FuncAlias_cv             18.53 %         18.48 %             5\n",
      "BM_FuncRestrict_mean        66062 ns        66061 ns            5\n",
      "BM_FuncRestrict_median      64442 ns        64440 ns            5\n",
      "BM_FuncRestrict_stddev       4089 ns         4089 ns            5\n",
      "BM_FuncRestrict_cv           6.19 %          6.19 %             5\n"
     ]
    }
   ],
   "source": [
    "! cd pointer_aliasing && ./bench_alias --benchmark_repetitions=5 --benchmark_report_aggregates_only=true"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2025-10-09T10:11:29+08:00\n",
      "Running ./bench_alias\n",
      "Run on (16 X 3792.93 MHz CPU s)\n",
      "CPU Caches:\n",
      "  L1 Data 32 KiB (x8)\n",
      "  L1 Instruction 32 KiB (x8)\n",
      "  L2 Unified 1024 KiB (x8)\n",
      "  L3 Unified 16384 KiB (x1)\n",
      "Load Average: 0.74, 0.57, 0.29\n",
      "-----------------------------------------------------------------\n",
      "Benchmark                       Time             CPU   Iterations\n",
      "-----------------------------------------------------------------\n",
      "BM_FuncAlias_mean           63741 ns        63731 ns            5\n",
      "BM_FuncAlias_median         64121 ns        64118 ns            5\n",
      "BM_FuncAlias_stddev          1233 ns         1218 ns            5\n",
      "BM_FuncAlias_cv              1.93 %          1.91 %             5\n",
      "BM_FuncRestrict_mean        69937 ns        69889 ns            5\n",
      "BM_FuncRestrict_median      64570 ns        64568 ns            5\n",
      "BM_FuncRestrict_stddev      11796 ns        11826 ns            5\n",
      "BM_FuncRestrict_cv          16.87 %         16.92 %             5\n"
     ]
    }
   ],
   "source": [
    "! cd pointer_aliasing && ./bench_alias --benchmark_repetitions=5 --benchmark_report_aggregates_only=true"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "benchmark_alias.cpp:19:23: optimized: loop vectorized using 16 byte vectors\n",
      "benchmark_alias.cpp:19:23: optimized:  loop versioned for vectorization because of possible aliasing\n",
      "benchmark_alias.cpp:19:23: optimized: loop vectorized using 8 byte vectors\n",
      "benchmark_alias.cpp:26:23: optimized: loop vectorized using 16 byte vectors\n",
      "benchmark_alias.cpp:26:23: optimized: loop vectorized using 16 byte vectors\n",
      "/usr/include/c++/11/bits/stl_vector.h:361:25: optimized: basic block part vectorized using 16 byte vectors\n",
      "/usr/include/c++/11/bits/stl_vector.h:98:16: optimized: basic block part vectorized using 16 byte vectors\n",
      "/usr/include/c++/11/bits/stl_vector.h:361:25: optimized: basic block part vectorized using 16 byte vectors\n",
      "benchmark_alias.cpp:19:23: optimized: loop vectorized using 16 byte vectors\n",
      "benchmark_alias.cpp:19:23: optimized:  loop versioned for vectorization because of possible aliasing\n",
      "benchmark_alias.cpp:19:23: optimized: loop vectorized using 8 byte vectors\n",
      "/usr/include/c++/11/bits/stl_vector.h:361:25: optimized: basic block part vectorized using 16 byte vectors\n",
      "/usr/include/c++/11/bits/stl_vector.h:98:16: optimized: basic block part vectorized using 16 byte vectors\n",
      "/usr/include/c++/11/bits/stl_vector.h:361:25: optimized: basic block part vectorized using 16 byte vectors\n"
     ]
    }
   ],
   "source": [
    "! cd pointer_aliasing && g++ -O3 -fstrict-aliasing -fopt-info-vec benchmark_alias.cpp -lbenchmark -lpthread -o bench_alias"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **普通指针版本**：编译器担心指针 alias → 先“版本化再矢量化”，带来运行时检查与分支，性能和稳定性都受影响。\n",
    "- **`restrict` 版本**：编译器确信无别名 → 直接生成矢量化循环，省去版本化开销，从而获得更好的平均性能和更一致的延迟。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 循环展开（Loop unrolling）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| 存储方案                                           | 编译期尺寸信息                     | 内存布局                 | 指针别名风险                                   | 自动循环展开 / 向量化倾向                        | 备注                                                    |\n",
    "| -------------------------------------------------- | ---------------------------------- | ------------------------ | ---------------------------------------------- | ------------------------------------------------ | ------------------------------------------------------- |\n",
    "| `T[M][N]`（静态二维数组）                          | 完全已知 (`M`,`N` 为 `constexpr`)  | 连续，行主序             | 最低（函数形参可用 `T (&)[M][N]`，无额外别名） | ★★★★★  （编译器最易做完全展开和向量化）          | 需在编译期确定尺寸；大数组可能占用静态区或栈空间        |\n",
    "| `std::array<std::array<T, N>, M>`                  | 完全已知                           | 连续，行主序             | 极低（引用传参或 `std::span` 均可避免别名）    | ★★★★★                                            | 和静态数组生成的代码几乎相同，但语义更安全              |\n",
    "| 扁平 `std::vector<T>` + 手动索引 (`row * N + col`) | 尺寸通常运行时确定（可借模板固定） | 连续，行主序             | 低（传裸指针/`span` 可能增加别名疑虑）         | ★★★★☆（若循环边界在调用点可知，可部分/完全展开） | 支持运行时尺寸；可配合 `restrict`/`[[assume]]` 改善优化 |\n",
    "| `std::vector<std::vector<T>>`                      | 运行时尺寸，行宽可变               | 每行单独分配，整体不连续 | 高（每行指针彼此独立）                         | ★★☆☆☆（常触发循环版本化或放弃向量化）            | 适合不规则矩阵；若追求性能，应避免                      |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [],
   "source": [
    "! cd loop_unrolling && g++ -O3 benchmark_matrix.cpp -lbenchmark -lpthread -o benchmark_matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2025-10-09T10:23:40+08:00\n",
      "Running ./benchmark_matrix\n",
      "Run on (16 X 3792.93 MHz CPU s)\n",
      "CPU Caches:\n",
      "  L1 Data 32 KiB (x8)\n",
      "  L1 Instruction 32 KiB (x8)\n",
      "  L2 Unified 1024 KiB (x8)\n",
      "  L3 Unified 16384 KiB (x1)\n",
      "Load Average: 0.18, 0.20, 0.21\n",
      "--------------------------------------------------------------------------\n",
      "Benchmark                Time             CPU   Iterations UserCounters...\n",
      "--------------------------------------------------------------------------\n",
      "BM_StaticArray        2888 ns         2888 ns       239674 items_per_second=5.67411G/s\n",
      "BM_Array2D            2072 ns         2072 ns       340085 items_per_second=7.90616G/s\n",
      "BM_FlatVector         1886 ns         1886 ns       363033 items_per_second=8.68773G/s\n",
      "BM_NestedVector       1328 ns         1328 ns       534088 items_per_second=12.3373G/s\n"
     ]
    }
   ],
   "source": [
    "! cd loop_unrolling && ./benchmark_matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2025-10-09T10:26:41+08:00\n",
      "Running ./benchmark_matrix\n",
      "Run on (16 X 3792.93 MHz CPU s)\n",
      "CPU Caches:\n",
      "  L1 Data 32 KiB (x8)\n",
      "  L1 Instruction 32 KiB (x8)\n",
      "  L2 Unified 1024 KiB (x8)\n",
      "  L3 Unified 16384 KiB (x1)\n",
      "Load Average: 0.14, 0.25, 0.23\n",
      "---------------------------------------------------------------------------------\n",
      "Benchmark                       Time             CPU   Iterations UserCounters...\n",
      "---------------------------------------------------------------------------------\n",
      "BM_StaticArray_mean          3129 ns         3129 ns            5 items_per_second=5.23678G/s\n",
      "BM_StaticArray_median        3132 ns         3132 ns            5 items_per_second=5.2319G/s\n",
      "BM_StaticArray_stddev        20.4 ns         20.4 ns            5 items_per_second=34.1528M/s\n",
      "BM_StaticArray_cv            0.65 %          0.65 %             5 items_per_second=0.65%\n",
      "BM_Array2D_mean              2107 ns         2107 ns            5 items_per_second=7.77581G/s\n",
      "BM_Array2D_median            2112 ns         2112 ns            5 items_per_second=7.75856G/s\n",
      "BM_Array2D_stddev            13.5 ns         13.5 ns            5 items_per_second=49.7343M/s\n",
      "BM_Array2D_cv                0.64 %          0.64 %             5 items_per_second=0.64%\n",
      "BM_FlatVector_mean           1896 ns         1896 ns            5 items_per_second=8.64207G/s\n",
      "BM_FlatVector_median         1894 ns         1894 ns            5 items_per_second=8.6493G/s\n",
      "BM_FlatVector_stddev         12.8 ns         12.8 ns            5 items_per_second=58.1698M/s\n",
      "BM_FlatVector_cv             0.67 %          0.68 %             5 items_per_second=0.67%\n",
      "BM_NestedVector_mean         1402 ns         1402 ns            5 items_per_second=11.7664G/s\n",
      "BM_NestedVector_median       1331 ns         1331 ns            5 items_per_second=12.3081G/s\n",
      "BM_NestedVector_stddev        137 ns          137 ns            5 items_per_second=1043.58M/s\n",
      "BM_NestedVector_cv           9.79 %          9.79 %             5 items_per_second=8.87%\n"
     ]
    }
   ],
   "source": [
    "! cd loop_unrolling && ./benchmark_matrix --benchmark_repetitions=5 --benchmark_report_aggregates_only=true"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [],
   "source": [
    "! cd loop_unrolling && g++ -O3 -fopt-info-vec -fopt-info-loop -Rpass=loop-vectorize benchmark_matrix.cpp -lbenchmark -lpthread -o benchmark_matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| 选项                    | 适用编译器                | 作用                                                         |\n",
    "| ----------------------- | ------------------------- | ------------------------------------------------------------ |\n",
    "| `-fopt-info-vec`        | GCC (包括 g++)            | 输出与“向量化”相关的优化信息：哪些循环成功向量化、在什么位置、使用了哪条路径等。 |\n",
    "| `-fopt-info-loop`       | GCC                       | 输出更广泛的循环优化信息：循环展开、循环并行化、删除空循环、分支剥离等。 |\n",
    "| `-Rpass=loop-vectorize` | Clang/LLVM (包括 clang++) | 在成功执行特定“pass”时给出提示。这里 `loop-vectorize` pass 负责循环向量化。编译通过时会打印出成功向量化的源代码行号。 |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2025-10-09T10:35:29+08:00\n",
      "Running ./benchmark_matrix\n",
      "Run on (16 X 3792.93 MHz CPU s)\n",
      "CPU Caches:\n",
      "  L1 Data 32 KiB (x8)\n",
      "  L1 Instruction 32 KiB (x8)\n",
      "  L2 Unified 1024 KiB (x8)\n",
      "  L3 Unified 16384 KiB (x1)\n",
      "Load Average: 0.98, 0.55, 0.36\n",
      "---------------------------------------------------------------------------------\n",
      "Benchmark                       Time             CPU   Iterations UserCounters...\n",
      "---------------------------------------------------------------------------------\n",
      "BM_StaticArray_mean          3463 ns         3463 ns            5 items_per_second=4.73187G/s\n",
      "BM_StaticArray_median        3462 ns         3462 ns            5 items_per_second=4.73284G/s\n",
      "BM_StaticArray_stddev        23.8 ns         23.8 ns            5 items_per_second=32.4338M/s\n",
      "BM_StaticArray_cv            0.69 %          0.69 %             5 items_per_second=0.69%\n",
      "BM_Array2D_mean              2228 ns         2228 ns            5 items_per_second=7.46344G/s\n",
      "BM_Array2D_median            2094 ns         2094 ns            5 items_per_second=7.82355G/s\n",
      "BM_Array2D_stddev             332 ns          332 ns            5 items_per_second=928.392M/s\n",
      "BM_Array2D_cv               14.91 %         14.90 %             5 items_per_second=12.44%\n",
      "BM_FlatVector_mean           1910 ns         1910 ns            5 items_per_second=8.58103G/s\n",
      "BM_FlatVector_median         1913 ns         1913 ns            5 items_per_second=8.56636G/s\n",
      "BM_FlatVector_stddev         23.7 ns         23.7 ns            5 items_per_second=107.017M/s\n",
      "BM_FlatVector_cv             1.24 %          1.24 %             5 items_per_second=1.25%\n",
      "BM_NestedVector_mean         1320 ns         1320 ns            5 items_per_second=12.4142G/s\n",
      "BM_NestedVector_median       1320 ns         1320 ns            5 items_per_second=12.4125G/s\n",
      "BM_NestedVector_stddev       9.10 ns         9.10 ns            5 items_per_second=85.6871M/s\n",
      "BM_NestedVector_cv           0.69 %          0.69 %             5 items_per_second=0.69%\n"
     ]
    }
   ],
   "source": [
    "! cd loop_unrolling && ./benchmark_matrix --benchmark_repetitions=5 --benchmark_report_aggregates_only=true --benchmark_filter=.*"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2025-10-09T10:36:03+08:00\n",
      "Running ./benchmark_matrix\n",
      "Run on (16 X 3792.93 MHz CPU s)\n",
      "CPU Caches:\n",
      "  L1 Data 32 KiB (x8)\n",
      "  L1 Instruction 32 KiB (x8)\n",
      "  L2 Unified 1024 KiB (x8)\n",
      "  L3 Unified 16384 KiB (x1)\n",
      "Load Average: 0.70, 0.42, 0.31\n",
      "---------------------------------------------------------------------------------\n",
      "Benchmark                       Time             CPU   Iterations UserCounters...\n",
      "---------------------------------------------------------------------------------\n",
      "BM_StaticArray_mean          2964 ns         2964 ns           10 items_per_second=5.53071G/s\n",
      "BM_StaticArray_median        2944 ns         2944 ns           10 items_per_second=5.56466G/s\n",
      "BM_StaticArray_stddev        64.8 ns         64.8 ns           10 items_per_second=117.806M/s\n",
      "BM_StaticArray_cv            2.19 %          2.19 %            10 items_per_second=2.13%\n",
      "BM_Array2D_mean              2250 ns         2250 ns           10 items_per_second=7.3447G/s\n",
      "BM_Array2D_median            2162 ns         2162 ns           10 items_per_second=7.57741G/s\n",
      "BM_Array2D_stddev             243 ns          243 ns           10 items_per_second=634.136M/s\n",
      "BM_Array2D_cv               10.80 %         10.80 %            10 items_per_second=8.63%\n",
      "BM_FlatVector_mean           2011 ns         2011 ns           10 items_per_second=8.21197G/s\n",
      "BM_FlatVector_median         1950 ns         1950 ns           10 items_per_second=8.40281G/s\n",
      "BM_FlatVector_stddev          210 ns          210 ns           10 items_per_second=680.284M/s\n",
      "BM_FlatVector_cv            10.42 %         10.42 %            10 items_per_second=8.28%\n",
      "BM_NestedVector_mean         1404 ns         1404 ns           10 items_per_second=11.7664G/s\n",
      "BM_NestedVector_median       1352 ns         1352 ns           10 items_per_second=12.1173G/s\n",
      "BM_NestedVector_stddev        149 ns          149 ns           10 items_per_second=990.904M/s\n",
      "BM_NestedVector_cv          10.60 %         10.60 %            10 items_per_second=8.42%\n"
     ]
    }
   ],
   "source": [
    "! cd loop_unrolling && ./benchmark_matrix --benchmark_repetitions=10 --benchmark_report_aggregates_only=true --benchmark_filter=.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# lambda_vs_bind"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [],
   "source": [
    "! cd lambda_vs_bind && g++ -O3 benchmark_lambda_vs_bind.cpp -lbenchmark -lpthread -o bench_lambda_vs_bind"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2025-10-09T10:43:06+08:00\n",
      "Running ./bench_lambda_vs_bind\n",
      "Run on (16 X 3792.93 MHz CPU s)\n",
      "CPU Caches:\n",
      "  L1 Data 32 KiB (x8)\n",
      "  L1 Instruction 32 KiB (x8)\n",
      "  L2 Unified 1024 KiB (x8)\n",
      "  L3 Unified 16384 KiB (x1)\n",
      "Load Average: 0.60, 0.40, 0.35\n",
      "------------------------------------------------------------------\n",
      "Benchmark                        Time             CPU   Iterations\n",
      "------------------------------------------------------------------\n",
      "BM_DirectCall                  238 ns          238 ns      2760530\n",
      "BM_LambdaCall                  237 ns          237 ns      2927974\n",
      "BM_BindCall                    246 ns          246 ns      2874948\n",
      "BM_BindCallPlaceholders        238 ns          238 ns      2812804\n"
     ]
    }
   ],
   "source": [
    "! cd lambda_vs_bind && ./bench_lambda_vs_bind"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2025-10-09T10:44:12+08:00\n",
      "Running ./bench_lambda_vs_bind\n",
      "Run on (16 X 3792.93 MHz CPU s)\n",
      "CPU Caches:\n",
      "  L1 Data 32 KiB (x8)\n",
      "  L1 Instruction 32 KiB (x8)\n",
      "  L2 Unified 1024 KiB (x8)\n",
      "  L3 Unified 16384 KiB (x1)\n",
      "Load Average: 0.78, 0.49, 0.38\n",
      "-------------------------------------------------------------------------\n",
      "Benchmark                               Time             CPU   Iterations\n",
      "-------------------------------------------------------------------------\n",
      "BM_DirectCall_mean                    242 ns          242 ns           10\n",
      "BM_DirectCall_median                  236 ns          236 ns           10\n",
      "BM_DirectCall_stddev                 14.0 ns         14.0 ns           10\n",
      "BM_DirectCall_cv                     5.79 %          5.79 %            10\n",
      "BM_LambdaCall_mean                    234 ns          234 ns           10\n",
      "BM_LambdaCall_median                  226 ns          226 ns           10\n",
      "BM_LambdaCall_stddev                 20.1 ns         20.1 ns           10\n",
      "BM_LambdaCall_cv                     8.56 %          8.56 %            10\n",
      "BM_BindCall_mean                      228 ns          228 ns           10\n",
      "BM_BindCall_median                    228 ns          228 ns           10\n",
      "BM_BindCall_stddev                   3.82 ns         3.82 ns           10\n",
      "BM_BindCall_cv                       1.68 %          1.68 %            10\n",
      "BM_BindCallPlaceholders_mean          232 ns          232 ns           10\n",
      "BM_BindCallPlaceholders_median        228 ns          228 ns           10\n",
      "BM_BindCallPlaceholders_stddev       15.8 ns         15.8 ns           10\n",
      "BM_BindCallPlaceholders_cv           6.82 %          6.82 %            10\n"
     ]
    }
   ],
   "source": [
    "! cd lambda_vs_bind && ./bench_lambda_vs_bind --benchmark_repetitions=10 --benchmark_report_aggregates_only=true"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2025-10-09T10:43:29+08:00\n",
      "Running ./bench_lambda_vs_bind\n",
      "Run on (16 X 3792.93 MHz CPU s)\n",
      "CPU Caches:\n",
      "  L1 Data 32 KiB (x8)\n",
      "  L1 Instruction 32 KiB (x8)\n",
      "  L2 Unified 1024 KiB (x8)\n",
      "  L3 Unified 16384 KiB (x1)\n",
      "Load Average: 0.43, 0.37, 0.34\n",
      "-------------------------------------------------------------------------\n",
      "Benchmark                               Time             CPU   Iterations\n",
      "-------------------------------------------------------------------------\n",
      "BM_DirectCall_mean                    239 ns          239 ns           10\n",
      "BM_DirectCall_median                  233 ns          233 ns           10\n",
      "BM_DirectCall_stddev                 14.6 ns         14.6 ns           10\n",
      "BM_DirectCall_cv                     6.10 %          6.10 %            10\n",
      "BM_LambdaCall_mean                    236 ns          236 ns           10\n",
      "BM_LambdaCall_median                  235 ns          235 ns           10\n",
      "BM_LambdaCall_stddev                 1.58 ns         1.58 ns           10\n",
      "BM_LambdaCall_cv                     0.67 %          0.67 %            10\n",
      "BM_BindCall_mean                      242 ns          242 ns           10\n",
      "BM_BindCall_median                    235 ns          235 ns           10\n",
      "BM_BindCall_stddev                   16.1 ns         16.1 ns           10\n",
      "BM_BindCall_cv                       6.68 %          6.68 %            10\n",
      "BM_BindCallPlaceholders_mean          239 ns          239 ns           10\n",
      "BM_BindCallPlaceholders_median        233 ns          233 ns           10\n",
      "BM_BindCallPlaceholders_stddev       16.9 ns         16.9 ns           10\n",
      "BM_BindCallPlaceholders_cv           7.06 %          7.06 %            10\n"
     ]
    }
   ],
   "source": [
    "! cd lambda_vs_bind && ./bench_lambda_vs_bind --benchmark_repetitions=10 --benchmark_report_aggregates_only=true --benchmark_filter=.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 返回值优化（RVO / NRVO）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| 术语 | 全称                            | 触发条件                                  | 是否强制               | 典型用法                        | 是否会因 `-fno-elide-constructors` 失效 |\n",
    "| ---- | ------------------------------- | ----------------------------------------- | ---------------------- | ------------------------------- | --------------------------------------- |\n",
    "| RVO  | Return Value Optimization       | `return Foo(...)` 返回一个临时（prvalue） | **C++17 起强制**       | 工厂函数直接 `return T{...};`   | 否                                      |\n",
    "| NRVO | Named Return Value Optimization | `return obj;` 返回函数内命名局部对象      | 可选优化（依赖编译器） | 在函数内构造局部变量再 `return` | 是（会退化成 move/copy）                |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 常规编译，允许优化器执行 RVO/NRVO"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [],
   "source": [
    "! cd rvo && g++ -O3 rvo_demo.cpp -lbenchmark -lpthread -o rvo_demo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [],
   "source": [
    "! cd rvo && ./rvo_demo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 禁用拷贝省略"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [],
   "source": [
    "! cd rvo && g++ -O3 -fno-elide-constructors rvo_demo.cpp -lbenchmark -lpthread -o rvo_demo"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [],
   "source": [
    "! cd rvo && ./rvo_demo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "|                              | 编译选项                  | constructions | copies | moves | 说明                                      |\n",
    "| ---------------------------- | ------------------------- | ------------- | ------ | ----- | ----------------------------------------- |\n",
    "| `make_tracker_rvo()`         | 默认优化                  | 1             | 0      | 0     | 返回临时对象，触发 C++17 强制 RVO。       |\n",
    "| `make_tracker_rvo()`         | `-fno-elide-constructors` | 1             | 0      | 0     | 即使禁用省略也无拷贝/移动，验证强制 RVO。 |\n",
    "| `make_tracker_nrvo()`        | 默认优化                  | 1             | 0      | 0     | 命名返回值在默认设置下成功 NRVO。         |\n",
    "| `make_tracker_nrvo()`        | `-fno-elide-constructors` | 1             | 0      | 1     | 关闭省略后 NRVO 失效，转为一次移动构造。  |\n",
    "| `make_tracker_with_move()`   | 默认优化                  | 1             | 0      | 1     | 显式 `std::move` 禁用 NRVO，只能移动。    |\n",
    "| `make_tracker_with_move()`   | `-fno-elide-constructors` | 1             | 0      | 1     | 行为相同；NRVO 本就被 `std::move` 阻断。  |\n",
    "| `make_tracker_branch(true)`  | 默认优化                  | 2             | 0      | 1     | 分支返回，无全局 NRVO，仅能移动其中一份。 |\n",
    "| `make_tracker_branch(true)`  | `-fno-elide-constructors` | 2             | 0      | 1     | 关闭省略对该结构无额外影响。              |\n",
    "| `make_tracker_branch(false)` | 默认优化                  | 2             | 0      | 1     | 与 `true` 分支对称。                      |\n",
    "| `make_tracker_branch(false)` | `-fno-elide-constructors` | 2             | 0      | 1     | 同上。                                    |\n",
    "\n",
    "- `make_tracker_rvo()` 体现了 **强制性 RVO**：即使显式禁用拷贝省略也不会产生移动或拷贝。\n",
    "- `make_tracker_nrvo()` 说明 **NRVO 仍属可选优化**：在默认情况下优化生效，禁用后需要一次移动。\n",
    "- 显式 `std::move` 或返回分支中的不同对象都会阻断 NRVO，因此在两种编译设置下移动次数一致。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# branching"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "用于比较“带分支”的更新逻辑与“无分支（利用算术与数组索引）”的实现之间的性能差异。程序会生成大量随机成交（fill），分别执行两种实现多次，统计并打印每次运行用时（微秒/纳秒），同时保留结果以避免被编译器优化掉。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [],
   "source": [
    "! cd branching && g++ -O3 benchmark_branch.cpp -lbenchmark -lpthread -o benchmark_branch"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2025-10-09T11:17:20+08:00\n",
      "Running ./benchmark_branch\n",
      "Run on (16 X 3792.93 MHz CPU s)\n",
      "CPU Caches:\n",
      "  L1 Data 32 KiB (x8)\n",
      "  L1 Instruction 32 KiB (x8)\n",
      "  L2 Unified 1024 KiB (x8)\n",
      "  L3 Unified 16384 KiB (x1)\n",
      "Load Average: 0.16, 0.16, 0.17\n",
      "-----------------------------------------------------------------------------------\n",
      "Benchmark                         Time             CPU   Iterations UserCounters...\n",
      "-----------------------------------------------------------------------------------\n",
      "BM_WithBranching/1000000 19702820550761 ns      5769838 ns            1 items_per_second=173.315M/s\n",
      "BM_WithBranching/5000000 19702847484752 ns     32713124 ns            1 items_per_second=152.844M/s\n",
      "BM_Branchless/1000000    19702911888768 ns     97078663 ns            1 items_per_second=10.3009M/s\n",
      "BM_Branchless/5000000    19702928111428 ns    113302583 ns            1 items_per_second=44.1296M/s\n"
     ]
    }
   ],
   "source": [
    "! cd branching && ./benchmark_branch"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2025-10-09T11:22:56+08:00\n",
      "Running ./benchmark_branch\n",
      "Run on (16 X 3792.93 MHz CPU s)\n",
      "CPU Caches:\n",
      "  L1 Data 32 KiB (x8)\n",
      "  L1 Instruction 32 KiB (x8)\n",
      "  L2 Unified 1024 KiB (x8)\n",
      "  L3 Unified 16384 KiB (x1)\n",
      "Load Average: 0.92, 0.39, 0.25\n",
      "-----------------------------------------------------------------------------------\n",
      "Benchmark                         Time             CPU   Iterations UserCounters...\n",
      "-----------------------------------------------------------------------------------\n",
      "BM_WithBranching/1000000 20039173608862 ns      5207690 ns            1 items_per_second=192.024M/s\n",
      "BM_WithBranching/5000000 20039200588891 ns     32187514 ns            1 items_per_second=155.34M/s\n",
      "BM_Branchless/1000000    20039276311387 ns    107853303 ns            1 items_per_second=9.27185M/s\n",
      "BM_Branchless/5000000    20039291150033 ns    122693958 ns            1 items_per_second=40.7518M/s\n"
     ]
    }
   ],
   "source": [
    "! cd branching && ./benchmark_branch"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2025-10-09T11:23:11+08:00\n",
      "Running ./benchmark_branch\n",
      "Run on (16 X 3792.93 MHz CPU s)\n",
      "CPU Caches:\n",
      "  L1 Data 32 KiB (x8)\n",
      "  L1 Instruction 32 KiB (x8)\n",
      "  L2 Unified 1024 KiB (x8)\n",
      "  L3 Unified 16384 KiB (x1)\n",
      "Load Average: 0.72, 0.37, 0.24\n",
      "------------------------------------------------------------------------------------------\n",
      "Benchmark                                Time             CPU   Iterations UserCounters...\n",
      "------------------------------------------------------------------------------------------\n",
      "BM_WithBranching/1000000_mean   20053916273053 ns     63814899 ns           10 items_per_second=35.2202M/s\n",
      "BM_WithBranching/1000000_median 20053917988982 ns     65528396 ns           10 items_per_second=15.3633M/s\n",
      "BM_WithBranching/1000000_stddev   35585584 ns     35579730 ns           10 items_per_second=55.0794M/s\n",
      "BM_WithBranching/1000000_cv           0.00 %         55.75 %            10 items_per_second=156.39%\n",
      "BM_WithBranching/5000000_mean   20054351165010 ns    498704351 ns           10 items_per_second=13.5614M/s\n",
      "BM_WithBranching/5000000_median 20054352828096 ns    500367531 ns           10 items_per_second=10.0502M/s\n",
      "BM_WithBranching/5000000_stddev  236632740 ns    236633038 ns           10 items_per_second=9.5334M/s\n",
      "BM_WithBranching/5000000_cv           0.00 %         47.45 %            10 items_per_second=70.30%\n",
      "BM_Branchless/1000000_mean      20054804953485 ns    952487763 ns           10 items_per_second=1050.61k/s\n",
      "BM_Branchless/1000000_median    20054804617820 ns    952151971 ns           10 items_per_second=1050.27k/s\n",
      "BM_Branchless/1000000_stddev      26338790 ns     26342927 ns           10 items_per_second=29.065k/s\n",
      "BM_Branchless/1000000_cv              0.00 %          2.77 %            10 items_per_second=2.77%\n",
      "BM_Branchless/5000000_mean      20055153828710 ns   1301369830 ns           10 items_per_second=3.92939M/s\n",
      "BM_Branchless/5000000_median    20055152844604 ns   1300387635 ns           10 items_per_second=3.84772M/s\n",
      "BM_Branchless/5000000_stddev     203007493 ns    203007659 ns           10 items_per_second=627.231k/s\n",
      "BM_Branchless/5000000_cv              0.00 %         15.60 %            10 items_per_second=15.96%\n"
     ]
    }
   ],
   "source": [
    "! cd branching && ./benchmark_branch --benchmark_repetitions=10 --benchmark_report_aggregates_only=true"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2025-10-09T11:18:43+08:00\n",
      "Running ./benchmark_branch\n",
      "Run on (16 X 3792.93 MHz CPU s)\n",
      "CPU Caches:\n",
      "  L1 Data 32 KiB (x8)\n",
      "  L1 Instruction 32 KiB (x8)\n",
      "  L2 Unified 1024 KiB (x8)\n",
      "  L3 Unified 16384 KiB (x1)\n",
      "Load Average: 0.49, 0.24, 0.20\n",
      "------------------------------------------------------------------------------------------\n",
      "Benchmark                                Time             CPU   Iterations UserCounters...\n",
      "------------------------------------------------------------------------------------------\n",
      "BM_WithBranching/1000000_mean   19785697380069 ns     63333548 ns           10 items_per_second=33.2744M/s\n",
      "BM_WithBranching/1000000_median 19785698730607 ns     64679878 ns           10 items_per_second=15.5808M/s\n",
      "BM_WithBranching/1000000_stddev   35396181 ns     35392046 ns           10 items_per_second=48.2646M/s\n",
      "BM_WithBranching/1000000_cv           0.00 %         55.88 %            10 items_per_second=145.05%\n",
      "BM_WithBranching/5000000_mean   19786134263210 ns    500211796 ns           10 items_per_second=13.6826M/s\n",
      "BM_WithBranching/5000000_median 19786134618931 ns    500573829 ns           10 items_per_second=10.0519M/s\n",
      "BM_WithBranching/5000000_stddev  243412815 ns    243407614 ns           10 items_per_second=9.65916M/s\n",
      "BM_WithBranching/5000000_cv           0.00 %         48.66 %            10 items_per_second=70.59%\n",
      "BM_Branchless/1000000_mean      19786598759207 ns    964693122 ns           10 items_per_second=1037.32k/s\n",
      "BM_Branchless/1000000_median    19786598376182 ns    964310401 ns           10 items_per_second=1037.03k/s\n",
      "BM_Branchless/1000000_stddev      26765306 ns     26767246 ns           10 items_per_second=28.7986k/s\n",
      "BM_Branchless/1000000_cv              0.00 %          2.77 %            10 items_per_second=2.78%\n",
      "BM_Branchless/5000000_mean      19786955857568 ns   1321796746 ns           10 items_per_second=3.86706M/s\n",
      "BM_Branchless/5000000_median    19786956703002 ns   1322644670 ns           10 items_per_second=3.78285M/s\n",
      "BM_Branchless/5000000_stddev     203689313 ns    203688625 ns           10 items_per_second=613.321k/s\n",
      "BM_Branchless/5000000_cv              0.00 %         15.41 %            10 items_per_second=15.86%\n"
     ]
    }
   ],
   "source": [
    "! cd branching && ./benchmark_branch --benchmark_repetitions=10 --benchmark_report_aggregates_only=true --benchmark_filter=.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# depchain"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "比较“串行依赖式加法”（每一步都依赖上一步的结果）与“成对拆分的加法”（先做互不依赖的部分和，再合并）的性能差异，从而演示为何编译器/处理器会尝试通过指令调度来减少依赖深度。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [],
   "source": [
    "! cd depchain && g++ -O2 benchmark_depchain.cpp -lbenchmark -lpthread -o benchmark_depchain"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2025-10-09T11:30:55+08:00\n",
      "Running ./benchmark_depchain\n",
      "Run on (16 X 3792.93 MHz CPU s)\n",
      "CPU Caches:\n",
      "  L1 Data 32 KiB (x8)\n",
      "  L1 Instruction 32 KiB (x8)\n",
      "  L2 Unified 1024 KiB (x8)\n",
      "  L3 Unified 16384 KiB (x1)\n",
      "Load Average: 0.43, 0.26, 0.21\n",
      "---------------------------------------------------------------------------------\n",
      "Benchmark                       Time             CPU   Iterations UserCounters...\n",
      "---------------------------------------------------------------------------------\n",
      "BM_SequentialAdds/256  20517588601510 ns      2911278 ns            1 adds=439.669k/s dep_levels=439.669k/s\n",
      "BM_SequentialAdds/4096 20517588673713 ns      2982341 ns            1 adds=6.86709M/s dep_levels=6.86709M/s\n",
      "BM_PairwiseAdds/256    20517588876941 ns      3185659 ns            1 adds=401.801k/s dep_levels=241.08k/s\n",
      "BM_PairwiseAdds/4096   20517588904624 ns      3212849 ns            1 adds=6.3744M/s dep_levels=3.82464M/s\n"
     ]
    }
   ],
   "source": [
    "! cd depchain && ./benchmark_depchain"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [],
   "source": [
    "! cd depchain && g++ -O3 benchmark_depchain.cpp -lbenchmark -lpthread -o benchmark_depchain"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2025-10-09T11:31:12+08:00\n",
      "Running ./benchmark_depchain\n",
      "Run on (16 X 3792.93 MHz CPU s)\n",
      "CPU Caches:\n",
      "  L1 Data 32 KiB (x8)\n",
      "  L1 Instruction 32 KiB (x8)\n",
      "  L2 Unified 1024 KiB (x8)\n",
      "  L3 Unified 16384 KiB (x1)\n",
      "Load Average: 0.54, 0.29, 0.22\n",
      "---------------------------------------------------------------------------------\n",
      "Benchmark                       Time             CPU   Iterations UserCounters...\n",
      "---------------------------------------------------------------------------------\n",
      "BM_SequentialAdds/256  20535278292132 ns      2548010 ns            1 adds=502.353k/s dep_levels=502.353k/s\n",
      "BM_SequentialAdds/4096 20535278368684 ns      2623260 ns            1 adds=7.80708M/s dep_levels=7.80708M/s\n",
      "BM_PairwiseAdds/256    20535278637155 ns      2891720 ns            1 adds=442.643k/s dep_levels=265.586k/s\n",
      "BM_PairwiseAdds/4096   20535278663473 ns      2917668 ns            1 adds=7.0193M/s dep_levels=4.21158M/s\n"
     ]
    }
   ],
   "source": [
    "! cd depchain && ./benchmark_depchain"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2025-10-09T11:29:25+08:00\n",
      "Running ./benchmark_depchain\n",
      "Run on (16 X 3792.93 MHz CPU s)\n",
      "CPU Caches:\n",
      "  L1 Data 32 KiB (x8)\n",
      "  L1 Instruction 32 KiB (x8)\n",
      "  L2 Unified 1024 KiB (x8)\n",
      "  L3 Unified 16384 KiB (x1)\n",
      "Load Average: 0.13, 0.22, 0.20\n",
      "----------------------------------------------------------------------------------------\n",
      "Benchmark                              Time             CPU   Iterations UserCounters...\n",
      "----------------------------------------------------------------------------------------\n",
      "BM_SequentialAdds/256_mean    20428097524783 ns      3095114 ns           10 adds=413.585k/s dep_levels=413.585k/s\n",
      "BM_SequentialAdds/256_median  20428097527596 ns      3097702 ns           10 adds=413.21k/s dep_levels=413.21k/s\n",
      "BM_SequentialAdds/256_stddev       0.000 ns        27947 ns           10 adds=3.75032k/s dep_levels=3.75032k/s\n",
      "BM_SequentialAdds/256_cv            0.00 %          0.90 %            10 adds=0.91% dep_levels=0.91%\n",
      "BM_SequentialAdds/4096_mean   20428098146929 ns      3717154 ns           10 adds=5.53195M/s dep_levels=5.53195M/s\n",
      "BM_SequentialAdds/4096_median 20428098175151 ns      3745344 ns           10 adds=5.46886M/s dep_levels=5.46886M/s\n",
      "BM_SequentialAdds/4096_stddev      0.000 ns       244726 ns           10 adds=378.108k/s dep_levels=378.108k/s\n",
      "BM_SequentialAdds/4096_cv           0.00 %          6.58 %            10 adds=6.83% dep_levels=6.83%\n",
      "BM_PairwiseAdds/256_mean      20428098613520 ns      4183679 ns           10 adds=305.96k/s dep_levels=183.576k/s\n",
      "BM_PairwiseAdds/256_median    20428098615190 ns      4185297 ns           10 adds=305.833k/s dep_levels=183.5k/s\n",
      "BM_PairwiseAdds/256_stddev         0.000 ns        24510 ns           10 adds=1.79417k/s dep_levels=1076.5/s\n",
      "BM_PairwiseAdds/256_cv              0.00 %          0.59 %            10 adds=0.59% dep_levels=0.59%\n",
      "BM_PairwiseAdds/4096_mean     20428098985639 ns      4555878 ns           10 adds=4.50242M/s dep_levels=2.70145M/s\n",
      "BM_PairwiseAdds/4096_median   20428098993670 ns      4563832 ns           10 adds=4.48766M/s dep_levels=2.69259M/s\n",
      "BM_PairwiseAdds/4096_stddev       257347 ns       190623 ns           10 adds=189.328k/s dep_levels=113.597k/s\n",
      "BM_PairwiseAdds/4096_cv             0.00 %          4.18 %            10 adds=4.21% dep_levels=4.21%\n"
     ]
    }
   ],
   "source": [
    "! cd depchain && ./benchmark_depchain --benchmark_repetitions=10 --benchmark_report_aggregates_only=true --benchmark_filter=.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# vectorization"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [],
   "source": [
    "! cd vectorization && g++ -O3 -mavx2 -mfma benchmark_vec.cpp -lbenchmark -lpthread -o benchmark_vec"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2025-10-09T11:34:59+08:00\n",
      "Running ./benchmark_vec\n",
      "Run on (16 X 3792.93 MHz CPU s)\n",
      "CPU Caches:\n",
      "  L1 Data 32 KiB (x8)\n",
      "  L1 Instruction 32 KiB (x8)\n",
      "  L2 Unified 1024 KiB (x8)\n",
      "  L3 Unified 16384 KiB (x1)\n",
      "Load Average: 0.52, 0.34, 0.24\n",
      "-----------------------------------------------------------------------------\n",
      "Benchmark                   Time             CPU   Iterations UserCounters...\n",
      "-----------------------------------------------------------------------------\n",
      "BenchmarkScalar        189450 ns       189450 ns         3799 bytes=66.4183G/s\n",
      "BenchmarkUnrolled4     178370 ns       178370 ns         3881 bytes=70.5438G/s\n",
      "BenchmarkAVX2          177138 ns       177139 ns         4155 bytes=71.0341G/s\n"
     ]
    }
   ],
   "source": [
    "! cd vectorization && ./benchmark_vec"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2025-10-09T11:35:21+08:00\n",
      "Running ./benchmark_vec\n",
      "Run on (16 X 3792.93 MHz CPU s)\n",
      "CPU Caches:\n",
      "  L1 Data 32 KiB (x8)\n",
      "  L1 Instruction 32 KiB (x8)\n",
      "  L2 Unified 1024 KiB (x8)\n",
      "  L3 Unified 16384 KiB (x1)\n",
      "Load Average: 0.44, 0.33, 0.24\n",
      "------------------------------------------------------------------------------------\n",
      "Benchmark                          Time             CPU   Iterations UserCounters...\n",
      "------------------------------------------------------------------------------------\n",
      "BenchmarkScalar_mean          154040 ns       153994 ns           10 bytes=83.1718G/s\n",
      "BenchmarkScalar_median        154896 ns       154898 ns           10 bytes=81.2341G/s\n",
      "BenchmarkScalar_stddev         22003 ns        21930 ns           10 bytes=11.6422G/s\n",
      "BenchmarkScalar_cv             14.28 %         14.24 %            10 bytes=14.00%\n",
      "BenchmarkUnrolled4_mean       196250 ns       196246 ns           10 bytes=64.3856G/s\n",
      "BenchmarkUnrolled4_median     193954 ns       193943 ns           10 bytes=64.8798G/s\n",
      "BenchmarkUnrolled4_stddev      13775 ns        13777 ns           10 bytes=4.24849G/s\n",
      "BenchmarkUnrolled4_cv           7.02 %          7.02 %            10 bytes=6.60%\n",
      "BenchmarkAVX2_mean            230037 ns       230014 ns           10 bytes=55.5294G/s\n",
      "BenchmarkAVX2_median          237272 ns       237269 ns           10 bytes=53.0416G/s\n",
      "BenchmarkAVX2_stddev           29018 ns        29010 ns           10 bytes=7.3144G/s\n",
      "BenchmarkAVX2_cv               12.61 %         12.61 %            10 bytes=13.17%\n"
     ]
    }
   ],
   "source": [
    "! cd vectorization && ./benchmark_vec --benchmark_repetitions=10 --benchmark_report_aggregates_only=true --benchmark_filter=.*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 常量折叠（Constant folding）和常量传播（Constant propagation）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 常量折叠：编译器在编译阶段计算可求值的表达式，并用常量替换，以减少运行时开销。\n",
    "- 常量传播：编译器将已知常量值沿数据流向后续语句传播，使更多优化（如死代码删除、循环展开、进一步的常量折叠）得以实现。\n",
    "- 实际项目中，无需手动介入，保持代码清晰即可；编译器会自动尝试这些优化。只有当你想阻止优化（例如调试、验证行为、或处理 volatile/I/O）时需要特殊处理。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "19.635\n"
     ]
    }
   ],
   "source": [
    "// 常量折叠示例\n",
    "\n",
    "#include <iostream>\n",
    "\n",
    "double compute_area() {\n",
    "    constexpr double pi = 3.14159265358979323846;\n",
    "    constexpr double radius = 2.5;\n",
    "\n",
    "    // 表达式只依赖 constexpr 常量，编译器会在编译期直接算出数值。\n",
    "    double area = pi * radius * radius;  // 常量折叠\n",
    "    return area;                         // 实际返回的是编译期的字面量\n",
    "}\n",
    "\n",
    "{\n",
    "    std::cout << compute_area() << '\\n';\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// 常量传播示例\n",
    "\n",
    "#include <cstdint>\n",
    "#include <iostream>\n",
    "\n",
    "std::uint32_t sum_fixed_range() {\n",
    "    const std::uint32_t start = 0;\n",
    "    const std::uint32_t end   = 4;\n",
    "    std::uint32_t total = 0;\n",
    "\n",
    "    for (std::uint32_t i = start; i < end; ++i) {\n",
    "        total += i * 10;\n",
    "    }\n",
    "    return total;  // 在高优化级别下，编译器会直接返回 60\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "sum_fixed_range(): 60\n",
      "sum_partially_known(5):  10\n",
      "sum_partially_known(15): 30\n"
     ]
    }
   ],
   "source": [
    "std::uint32_t sum_partially_known(std::uint32_t dynamic_limit) {\n",
    "    const std::uint32_t base = 5;\n",
    "    std::uint32_t total = base;  // base 被传播到后续代码\n",
    "    if (dynamic_limit > 10) {\n",
    "        total += base * 2;       // 等价于 total += 10\n",
    "    }\n",
    "    return total + dynamic_limit;\n",
    "}\n",
    "\n",
    "{\n",
    "    std::cout << \"sum_fixed_range(): \" << sum_fixed_range() << '\\n';\n",
    "    std::cout << \"sum_partially_known(5):  \"\n",
    "              << sum_partially_known(5) << '\\n';\n",
    "    std::cout << \"sum_partially_known(15): \"\n",
    "              << sum_partially_known(15) << '\\n';\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 76,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "// 常量折叠 + 传播触发的循环展开示例\n",
    "\n",
    "#include <array>\n",
    "#include <cstdint>\n",
    "#include <iostream>\n",
    "\n",
    "constexpr std::size_t kSteps = 4;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 77,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "loop_example(): 10\n"
     ]
    }
   ],
   "source": [
    "std::uint32_t loop_example() {\n",
    "    std::array<std::uint32_t, kSteps> vals{1, 2, 3, 4};\n",
    "\n",
    "    std::uint32_t total = 0;\n",
    "    for (std::size_t i = 0; i < kSteps; ++i) {\n",
    "        total += vals[i];\n",
    "    }\n",
    "    return total;  // 在 -O2/-O3 下通常直接返回 10\n",
    "}\n",
    "\n",
    "{\n",
    "    std::cout << \"loop_example(): \" << loop_example() << '\\n';\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 死代码消除（Dead Code Elimination，DCE）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "死代码消除（Dead Code Elimination, DCE）的核心在于 **找出不会影响程序可观察行为的代码**，然后将它删除。为了做到这一点，编译器通常会进行两类分析：**可达性分析（Reachability Analysis）** 和 **存活性分析（Liveness Analysis）**。这两个分析覆盖了“永远不会执行”以及“执行了也没用”两大类死代码。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# TODO: 尾调用优化（Tail call optimization）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 额外的循环优化"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "循环展开是编译器采用的主要循环相关优化技术，但还有其他的循环优化方法：\n",
    "\n",
    "- 循环裂变（Loop fission）将一个循环分解为多个对较小数据集进行操作的循环，以提高缓存引用的局部性。\n",
    "- 循环融合（Loop fusion）则相反，如果两个相邻循环执行次数相同，可以将它们合并为一个，以减少循环开销。\n",
    "- 循环倒置（Loop inversion）是一种将`while`循环转换为`if`条件语句内部的`do-while`循环的技术。这样在循环执行时，跳转总数会减少两次，通常适用于预计至少会执行一次的循环。\n",
    "- 循环交换（Loop interchange）会交换内循环和外循环，尤其是在这样做能提高缓存引用局部性的情况下——例如，在遍历数组时，连续访问内存会对性能产生巨大影响。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# TODO: 循环不变代码外提（Loop invariant code movement）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# placement new"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在 C++ 中，`new` 表达式通常做两件事：\n",
    "\n",
    "1. **分配内存**（调用内存分配函数，通常是 `operator new`）。\n",
    "2. **在分配的内存上构造对象**（调用对象的构造函数）。\n",
    "\n",
    "而 **placement new** 是 `new` 的一种特殊用法，它 **跳过内存分配**，只负责 **在指定的内存地址上调用构造函数**。也就是说，我们先自行提供一块足够大的、对齐正确的内存，再用 placement new 在这块内存上构造对象。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [],
   "source": [
    "new (pointer) Type(args...); // 其中 `pointer` 是一块已经分配好、对齐满足要求的内存地址。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "placement new 是 C++ 提供的一种控制对象构造位置的机制，它将内存分配与对象构造解耦，使得我们可以在特定的内存区域（如自定义内存池）构造对象。然而，使用时需要谨慎处理内存对齐、对象析构和内存生命周期，遵循 RAII 思想，以避免出现未定义行为。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "经典用法场景\n",
    "\n",
    "- **在预分配的内存中构造多个对象**（如内存池、对象池）。\n",
    "- **自定义容器的内部存储管理**。\n",
    "- **在特定内存区域（例如共享内存、嵌入式内存区域）构造对象**。\n",
    "- **细粒度地控制对象生命周期**，如构造-析构但不释放内存。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "vscode": {
     "languageId": "cpp"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Widget constructed: (42, 3.14)\n",
      "w->x = 42, w->y = 3.14\n",
      "Widget destructed.\n",
      "Widget constructed: (7, 2.71)\n",
      "w2->x = 7, w2->y = 2.71\n",
      "Widget destructed.\n"
     ]
    }
   ],
   "source": [
    "#include <new>      // std::launder, placement new\n",
    "#include <cstring>  // std::memset\n",
    "#include <iostream>\n",
    "\n",
    "struct Widget {\n",
    "    int x;\n",
    "    double y;\n",
    "\n",
    "    Widget(int xVal, double yVal) : x{xVal}, y{yVal} {\n",
    "        std::cout << \"Widget constructed: (\" << x << \", \" << y << \")\\n\";\n",
    "    }\n",
    "\n",
    "    ~Widget() {\n",
    "        std::cout << \"Widget destructed.\\n\";\n",
    "    }\n",
    "};\n",
    "\n",
    "{\n",
    "    // 预先分配一块足够大的缓冲区\n",
    "    alignas(Widget) unsigned char buffer[sizeof(Widget)];\n",
    "\n",
    "    // 使用 placement new 在缓冲区上构造对象\n",
    "    Widget* w = new (buffer) Widget(42, 3.14);\n",
    "\n",
    "    // 使用对象\n",
    "    std::cout << \"w->x = \" << w->x << \", w->y = \" << w->y << '\\n';\n",
    "\n",
    "    // 手动调用析构函数（注意：不会自动释放 buffer 内存）\n",
    "    w->~Widget();\n",
    "\n",
    "    // 如果需要，可以重新利用这块内存构造另一个对象\n",
    "    std::memset(buffer, 0, sizeof(buffer));\n",
    "    Widget* w2 = new (buffer) Widget(7, 2.71);\n",
    "\n",
    "    std::cout << \"w2->x = \" << w2->x << \", w2->y = \" << w2->y << '\\n';\n",
    "    w2->~Widget(); // 再次显式析构\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- `alignas(Widget)` 确保缓冲区内存满足 `Widget` 对齐要求。\n",
    "- `new (buffer) Widget(...)` 在 `buffer` 上原地构造对象。\n",
    "- 使用完成后，需要显式调用析构函数 `w->~Widget()`。\n",
    "- `buffer` 属于静态或栈内存，因此无需调用 `operator delete`。\n",
    "- C++17 起，可以用 `std::launder` 保证对象重用时的指针有效性。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "与标准 `new` 的对比\n",
    "\n",
    "| 功能         | 常规 `new`                  | placement new                      |\n",
    "| ------------ | --------------------------- | ---------------------------------- |\n",
    "| 内存分配     | 自动（调用 `operator new`） | 需提前准备（自己管理内存）         |\n",
    "| 对象构造     | 自动                        | 在指定地址上构造                   |\n",
    "| 对象析构     | `delete` 自动析构并释放内存 | 必须显式调用析构函数；内存释放自理 |\n",
    "| 典型使用场景 | 一般对象构造                | 内存池、自定义容器、嵌入式系统等   |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "注意事项\n",
    "\n",
    "1. **确保内存对齐**：使用 `alignas` 或 `std::aligned_storage` 等保证目标类型的对齐要求。\n",
    "2. **手动析构**：placement new 构造的对象不会被自动析构，需显式调用析构函数。\n",
    "3. **内存管理责任**：对应的原始内存需由程序员管理，如使用 `std::array<unsigned char, N>` 或 `std::aligned_storage_t`。\n",
    "4. **与 `std::launder`**：如果在同一块内存上重新构造对象，C++17 推荐使用 `std::launder` 获取有效指针。\n",
    "5. **异常安全**：如果构造函数抛出异常，需考虑清理逻辑（释放或重置缓冲区）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# std::string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> - Linux多线程服务端编程:使用muduo C++网络库 : 第12章\n",
    "\n",
    "Scott Meyers 在《Effective STL》第 15 条将 `std::string` 的实现划分为三大类：\n",
    "\n",
    "1. **直接拷贝（Eager Copy）**<br/>\n",
    "使用与 `std::vector` 类似的“三指针”或“指针 + 长度/容量”结构，每次拷贝都复制整段字符数据，结构清晰、线程友好，但在频繁拷贝场景中开销较大。\n",
    "\n",
    "2. **写时复制（Copy-on-Write，COW）**<br/>\n",
    "仅存储指向共享缓冲区的指针，利用引用计数延迟真正的数据复制。复制成本低，但首个写操作可能退化为 `O(N)` 并且与多线程不兼容。libstdc++ 旧版 `std::string` 采用该方案。\n",
    "\n",
    "3. **短字符串优化（Small String Optimization，SSO）**<br/>\n",
    "在对象内部嵌入一段本地缓冲，短字符串完全驻留于对象内，避免堆分配；长字符串退化为堆分配。Visual C++、libc++ 等均采用某种形式的 SSO。实现需要巧妙地在同一内存区域复用指针/长度/容量与本地缓冲，复杂度最高。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **Eager Copy**：结构简单、线程安全，代码维护友好。\n",
    "- **COW**：节省复制成本但写入代价高，多线程下需要额外同步。\n",
    "- **SSO**：为短字符串消除动态分配，能显著提升常见工作负载的性能，但实现最复杂。\n",
    "\n",
    "在真实工程中，应结合字符串长度分布、线程模型和平台约束进行权衡，正如 Andrei Alexandrescu 所强调的，合理的选择可带来两位数百分比的整体性能收益。同时，避免为了模板技巧而牺牲可维护性——这与“过度使用 C++ 模板”的警示不谋而合。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 常见库的实现策略与对象大小\n",
    "\n",
    "| 库                 | 32-bit 大小 (字节)    | 64-bit 大小 (字节) | 主要策略            |\n",
    "| ------------------ | --------------------- | ------------------ | ------------------- |\n",
    "| g++ `std::string`  | 4                     | 8                  | COW                 |\n",
    "| GNU `__sso_string` | 24                    | 32                 | SSO                 |\n",
    "| SGI STL            | 12                    | 24                 | Eager Copy          |\n",
    "| clang libc++       | 12                    | 24                 | SSO（高空间利用率） |\n",
    "| Visual C++ 2010    | 28/32 (Debug/Release) | 40/48              | SSO                 |\n",
    "| Apache libstdcxx   | 4                     | 8                  | COW                 |\n",
    "\n",
    "> 调试版与发布版对象大小不同的库（如 Visual C++）禁止跨模式混用。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "重要实现要点\n",
    "\n",
    "- 无论哪种策略，都必须维护三类信息：指向字符数组的指针、当前长度、当前容量。\n",
    "- **Eager Copy** 可以通过缩小长度/容量字段的位宽（如使用 32 位整型）在 64 位平台上减小对象尺寸。\n",
    "- **COW** 在多核时代被批评为“不可扩展”；修改操作需要先分离专属缓冲。\n",
    "- **SSO** 需要位运算和联合体等技巧来辨识“短/长”模式；libc++ 通过重叠存储和首位标志实现 24 字节对象、22 字节内置缓冲。\n",
    "- Andrei Alexandrescu 建议：短字符串用 SSO，中等长度用 Eager Copy，超长字符串用 COW，具体阈值需靠性能分析确定。\n",
    "- 早期标准未确保 `std::string` 连续存储；实践中所有实现已达成共识，新标准也已确认这一点。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [],
   "source": [
    "! cd string && g++ -O3 string_variants_bench.cpp -lbenchmark -lpthread -o string_variants_bench"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2025-10-10T08:21:10+08:00\n",
      "Running ./string_variants_bench\n",
      "Run on (16 X 3792.92 MHz CPU s)\n",
      "CPU Caches:\n",
      "  L1 Data 32 KiB (x8)\n",
      "  L1 Instruction 32 KiB (x8)\n",
      "  L2 Unified 1024 KiB (x8)\n",
      "  L3 Unified 16384 KiB (x1)\n",
      "Load Average: 0.08, 0.10, 0.12\n",
      "-------------------------------------------------------------------------\n",
      "Benchmark                               Time             CPU   Iterations\n",
      "-------------------------------------------------------------------------\n",
      "BM_EagerStringSimpleAppend/8         55.5 ns         55.5 ns     12370395\n",
      "BM_EagerStringSimpleAppend/16        44.5 ns         44.5 ns     15833177\n",
      "BM_EagerStringSimpleAppend/32        33.4 ns         33.4 ns     21171078\n",
      "BM_EagerStringSimpleAppend/64        32.8 ns         32.8 ns     21450831\n",
      "BM_EagerStringSimpleAppend/128       33.0 ns         33.0 ns     21233206\n",
      "BM_EagerStringSimpleAppend/256       45.4 ns         45.4 ns     15467749\n",
      "BM_CowStringSimpleAppend/8           63.3 ns         63.3 ns     10850291\n",
      "BM_CowStringSimpleAppend/16          63.2 ns         63.2 ns     11180152\n",
      "BM_CowStringSimpleAppend/32          64.6 ns         64.6 ns     10731244\n",
      "BM_CowStringSimpleAppend/64          63.7 ns         63.7 ns     11140741\n",
      "BM_CowStringSimpleAppend/128         64.9 ns         64.9 ns     10839331\n",
      "BM_CowStringSimpleAppend/256         67.0 ns         67.0 ns     10354043\n",
      "BM_SsoStringSimpleAppend/1           8.06 ns         8.06 ns     87611270\n",
      "BM_SsoStringSimpleAppend/8           8.13 ns         8.13 ns     86686066\n",
      "BM_SsoStringSimpleAppend/19          16.3 ns         16.3 ns     42566369\n"
     ]
    }
   ],
   "source": [
    "! cd string && ./string_variants_bench"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 比较 std::vector、std::array、std::list 与 C 风格原生数组"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [],
   "source": [
    "! cd containers && g++ -std=c++17 -O2 benchmark_containers.cpp -lbenchmark -lpthread -o bench_containers"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2025-10-11T05:05:15+08:00\n",
      "Running ./bench_containers\n",
      "Run on (16 X 3792.95 MHz CPU s)\n",
      "CPU Caches:\n",
      "  L1 Data 32 KiB (x8)\n",
      "  L1 Instruction 32 KiB (x8)\n",
      "  L2 Unified 1024 KiB (x8)\n",
      "  L3 Unified 16384 KiB (x1)\n",
      "Load Average: 0.10, 0.10, 0.18\n",
      "--------------------------------------------------------------------------------\n",
      "Benchmark                      Time             CPU   Iterations UserCounters...\n",
      "--------------------------------------------------------------------------------\n",
      "Vector/Fill/k1K              577 ns          577 ns      1261659 bytes_per_second=6.61338G/s items_per_second=1.77526G/s\n",
      "Vector/Fill/k16K           11016 ns        11016 ns        63014 bytes_per_second=5.54058G/s items_per_second=1.48729G/s\n",
      "Vector/Fill/k256K         175872 ns       175862 ns         4013 bytes_per_second=5.55299G/s items_per_second=1.49062G/s\n",
      "Array/Fill/k1K               489 ns          489 ns      1474530 bytes_per_second=7.79971G/s items_per_second=2.09372G/s\n",
      "Array/Fill/k16K             4110 ns         4109 ns       172733 bytes_per_second=14.8523G/s items_per_second=3.98689G/s\n",
      "Array/Fill/k256K           70122 ns        70120 ns        10426 bytes_per_second=13.9271G/s items_per_second=3.73852G/s\n",
      "List/Fill/k1K              13154 ns        13154 ns        45141 bytes_per_second=296.971M/s items_per_second=77.8491M/s\n",
      "List/Fill/k16K            213448 ns       213448 ns         3270 bytes_per_second=292.811M/s items_per_second=76.7586M/s\n",
      "List/Fill/k256K          3556903 ns      3556791 ns          205 bytes_per_second=281.152M/s items_per_second=73.7024M/s\n",
      "CArray/Fill/k1K              289 ns          289 ns      2414575 bytes_per_second=13.221G/s items_per_second=3.54898G/s\n",
      "CArray/Fill/k16K            4159 ns         4159 ns       169883 bytes_per_second=14.6757G/s items_per_second=3.93948G/s\n",
      "CArray/Fill/k256K          68830 ns        68830 ns        10197 bytes_per_second=14.188G/s items_per_second=3.80856G/s\n",
      "Vector/SeqRead/k1K           240 ns          238 ns      3055771 bytes_per_second=16.0148G/s items_per_second=4.29895G/s\n",
      "Vector/SeqRead/k16K         4284 ns         4284 ns       164047 bytes_per_second=14.2479G/s items_per_second=3.82463G/s\n",
      "Vector/SeqRead/k256K       62703 ns        62703 ns        11454 bytes_per_second=15.5745G/s items_per_second=4.18074G/s\n",
      "Array/SeqRead/k1K            235 ns          235 ns      2963951 bytes_per_second=16.2564G/s items_per_second=4.36379G/s\n",
      "Array/SeqRead/k16K          4371 ns         4371 ns       162967 bytes_per_second=13.9648G/s items_per_second=3.74865G/s\n",
      "Array/SeqRead/k256K        62350 ns        62350 ns        11486 bytes_per_second=15.6625G/s items_per_second=4.20436G/s\n",
      "List/SeqRead/k1K            1078 ns         1078 ns       600194 bytes_per_second=3.53751G/s items_per_second=949.593M/s\n",
      "List/SeqRead/k16K          20976 ns        20976 ns        41945 bytes_per_second=2.90974G/s items_per_second=781.079M/s\n",
      "List/SeqRead/k256K        294846 ns       294846 ns         2507 bytes_per_second=3.31211G/s items_per_second=889.087M/s\n",
      "CArray/SeqRead/k1K           234 ns          234 ns      3082561 bytes_per_second=16.2826G/s items_per_second=4.37082G/s\n",
      "CArray/SeqRead/k16K         4292 ns         4292 ns       161077 bytes_per_second=14.2223G/s items_per_second=3.81776G/s\n",
      "CArray/SeqRead/k256K       60142 ns        60142 ns        11653 bytes_per_second=16.2376G/s items_per_second=4.35874G/s\n",
      "Vector/RandRead/k1K          457 ns          457 ns      1477782 bytes_per_second=8.3484G/s items_per_second=2.24101G/s\n",
      "Vector/RandRead/k16K        6172 ns         6172 ns       114817 bytes_per_second=9.88845G/s items_per_second=2.65441G/s\n",
      "Vector/RandRead/k256K     211949 ns       211950 ns         3633 bytes_per_second=4.60752G/s items_per_second=1.23682G/s\n",
      "Array/RandRead/k1K           260 ns          260 ns      2768319 bytes_per_second=14.676G/s items_per_second=3.93957G/s\n",
      "Array/RandRead/k16K         6079 ns         6079 ns       119214 bytes_per_second=10.0407G/s items_per_second=2.69528G/s\n",
      "Array/RandRead/k256K      196645 ns       196639 ns         3595 bytes_per_second=4.96628G/s items_per_second=1.33313G/s\n",
      "CArray/RandRead/k1K          262 ns          262 ns      2694048 bytes_per_second=14.5343G/s items_per_second=3.90152G/s\n",
      "CArray/RandRead/k16K        5864 ns         5864 ns       120187 bytes_per_second=10.4087G/s items_per_second=2.79406G/s\n",
      "CArray/RandRead/k256K     205084 ns       205084 ns         3469 bytes_per_second=4.76177G/s items_per_second=1.27823G/s\n"
     ]
    }
   ],
   "source": [
    "! cd containers && ./bench_containers"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "C++17",
   "version": "17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
